#include "StdAfx.h"
#include "TileGenerator.h"
#include "Voxelizer.h"
#include "HashComputer.h"


//#pragma optimize("", off)
//#pragma inline_depth(0)


namespace MNM
{
	static const int NeighbourOffset_TileGenerator[8][2] =
	{
		{ 0, 1},
		{-1, 0},
		{ 1, 0},
		{ 0,-1},
		{-1,-1},
		{ 1,-1},
		{ 1, 1},
		{-1, 1},
	};

	static uchar CornerTable[3][3][3] =
	{
		{	{ 0, 0, 1	}, 
			{	0, 0, 0 },
			{ 1, 1, 1 },
		},
		{	{ 0, 0, 1	},
			{	0, 0, 0 },
			{ 1, 0, 0 },
		},
		{	{ 1, 1, 0	},
			{	0, 0, 1 },
			{ 1, 0, 0 },
		},
	};

/* 

	Expanded, easier to read
	
	CornerTable[UW][UW][UW] = 0;
	CornerTable[UW][UW][NB] = 0;
	CornerTable[UW][UW][WB] = 1;
	CornerTable[UW][NB][UW] = 0;
	CornerTable[UW][NB][NB] = 0;
	CornerTable[UW][NB][WB] = 0;
	CornerTable[UW][WB][UW] = 1;
	CornerTable[UW][WB][NB] = 1;
	CornerTable[UW][WB][WB] = 1;

	CornerTable[NB][UW][UW] = 0;
	CornerTable[NB][UW][NB] = 0;
	CornerTable[NB][UW][WB] = 1;
	CornerTable[NB][NB][UW] = 0;
	CornerTable[NB][NB][NB] = 0;
	CornerTable[NB][NB][WB] = 0;
	CornerTable[NB][WB][UW] = 1;
	CornerTable[NB][WB][NB] = 0;
	CornerTable[NB][WB][WB] = 0;
	
	CornerTable[WB][UW][UW] = 1;
	CornerTable[WB][UW][NB] = 1;
	CornerTable[WB][UW][WB] = 0;
	CornerTable[WB][NB][UW] = 0;
	CornerTable[WB][NB][NB] = 0;
	CornerTable[WB][NB][WB] = 1;
	CornerTable[WB][WB][UW] = 1;
	CornerTable[WB][WB][NB] = 0;
	CornerTable[WB][WB][WB] = 0;
*/

	bool TileGenerator::Generate(const Params& params, Tile& tile, uint32* tileHash)
	{
		if ((params.sizeX > MaxTileSizeX) || (params.sizeY > MaxTileSizeY) || (params.sizeZ > MaxTileSizeZ))
			return false;

		const float MinVoxelSize = 0.025f;
		if ((params.voxelSize.x < MinVoxelSize) || (params.voxelSize.y < MinVoxelSize) || (params.voxelSize.z < MinVoxelSize))
			return false;

		m_params = params;
		m_profiler = ProfilerType();
		m_top = (size_t)(m_params.sizeZ / m_params.voxelSize.z + 0.10f);

		AABB aabb(m_params.origin, m_params.origin + Vec3i(m_params.sizeX, m_params.sizeY, m_params.sizeZ));

		if (m_params.boundary && !m_params.boundary->Overlaps(aabb))
			return false;

		const size_t border = BorderSizeH();
		const size_t borderV = BorderSizeV();
		if (border | borderV)
			aabb.Expand(Vec3(border * m_params.voxelSize.x, border * m_params.voxelSize.y, borderV * m_params.voxelSize.z));

		aabb.max.z += m_params.agent.height * m_params.voxelSize.z;

		bool fullyContained = true;

		if (m_params.boundary || m_params.exclusionCount)
		{
			for (size_t e = 0; e < m_params.exclusionCount; ++e)
			{
				BoundingVolume::ExtendedOverlap eoverlap = m_params.exclusions[e].Contains(aabb);

				if (eoverlap == BoundingVolume::FullOverlap)
					return false;
				else if (eoverlap == BoundingVolume::PartialOverlap)
					fullyContained = false;
			}

			BoundingVolume::ExtendedOverlap ioverlap = 
				m_params.boundary ? m_params.boundary->Contains(aabb) : BoundingVolume::FullOverlap;

			if (ioverlap == BoundingVolume::NoOverlap)
				return false;
			else if (ioverlap == BoundingVolume::PartialOverlap)
				fullyContained = false;
		}

		CompactSpanGrid().Swap(m_spanGrid);
		SpanExtraInfo().swap(m_distances);
		SpanExtraInfo().swap(m_labels);
		Regions().swap(m_regions);
		Polygons().swap(m_polygons);

		Vertices().swap(m_vertices);
		Triangles().swap(m_triangles);
		BVTree().swap(m_bvtree);

		CompactSpanGrid().Swap(m_spanGridFlagged);

		uint32 hashSeed = 0;
		if (fullyContained)
			hashSeed = 0xf007b00b;
		else
		{
			HashComputer hash;

			if (m_params.boundary || m_params.exclusionCount)
			{
				for (size_t e = 0; e < m_params.exclusionCount; ++e)
				{
					const BoundingVolume& volume = m_params.exclusions[e];
					const size_t vertexCount = volume.vertices.size();

					for (size_t v = 0; v < vertexCount; ++v)
						hash.Add(volume.vertices[v]);			

					hash.Add(volume.height);
				}

				if (m_params.boundary)
				{
					const BoundingVolume& volume = *m_params.boundary;
					const size_t vertexCount = volume.vertices.size();

					for (size_t v = 0; v < vertexCount; ++v)
						hash.Add(volume.vertices[v]);			

					hash.Add(volume.height);
				}
			}

			hash.Complete();
			hashSeed = hash.GetValue();
		}

		uint32 hashValue = 0;
		size_t triCount = VoxelizeVolume(aabb, hashSeed, &hashValue);

		if (tileHash)
			*tileHash = hashValue;

		if (!triCount)
			return false;

		tile.hashValue = hashValue;

		FilterWalkable(aabb, fullyContained);

		if (!m_spanGrid.GetSpanCount())
			return false;

		ComputeDistanceTransform();
		//BlurDistanceTransform();

		if (!ExtractContours())
			return false;

		FilterBadRegions(m_params.minWalkableArea);
		SimplifyContours();
		Triangulate();

		if (m_params.flags & Params::BuildBVTree)
			BuildBVTree();

		if (m_vertices.empty())
			return false;

		tile.CopyTriangles(&m_triangles.front(), m_triangles.size());
		tile.CopyVertices(&m_vertices.front(), m_vertices.size());

		if (m_params.flags & Params::BuildBVTree)
			tile.CopyNodes(&m_bvtree.front(), m_bvtree.size());

		return true;
	}

	const TileGenerator::ProfilerType& TileGenerator::GetProfiler() const
	{
		return m_profiler;
	}

	size_t TileGenerator::VoxelizeVolume(const AABB& volume, uint32 hashValueSeed, uint32* hashValue)
	{
		m_profiler.StartTimer(Voxelization);

		WorldVoxelizer voxelizer;

		voxelizer.Start(volume, m_params.voxelSize);
		size_t triCount = voxelizer.ProcessGeometry(hashValueSeed, 
			m_params.flags & Params::NoHashTest ? 0 : m_params.hashValue, hashValue);
		voxelizer.CalculateWaterDepth();

		m_profiler.AddMemory(DynamicSpanGridMemory, voxelizer.GetSpanGrid().GetMemoryUsage());

		m_spanGrid.BuildFrom(voxelizer.GetSpanGrid());

		m_profiler.StopTimer(Voxelization);
	
		m_profiler.AddMemory(CompactSpanGridMemory, m_spanGrid.GetMemoryUsage());
		m_profiler.FreeMemory(DynamicSpanGridMemory, voxelizer.GetSpanGrid().GetMemoryUsage());

		m_profiler.AddStat(VoxelizationTriCount, triCount);

		return triCount;
	}

	void TileGenerator::FilterWalkable(const AABB& aabb, bool fullyContained)
	{
		m_profiler.StartTimer(Filter);

		const size_t gridWidth = m_spanGrid.GetWidth();
		const size_t gridHeight = m_spanGrid.GetHeight();
		const size_t gridSize = gridWidth * gridHeight;

		const size_t heightVoxelCount = m_params.agent.height;
		const size_t climbableVoxelCount = m_params.agent.climbableHeight;

		const size_t extraHeight = m_params.agent.height;
		const size_t spaceTop = (2 * BorderSizeV()) + extraHeight + m_top;

		size_t nonWalkableCount = 0;

		// discard spans where dude wouldn't fit
		for (size_t i = 0; i < gridSize; ++i)
		{
			if (const CompactSpanGrid::Cell cell = m_spanGrid[i])
			{
				size_t count = cell.count;

				for (size_t s = 0; s < count; ++s)
				{
					CompactSpanGrid::Span& span = m_spanGrid.GetSpan(cell.index + s);

					if (span.backface || span.depth > m_params.agent.maxWaterDepth)
					{
						span.flags |= NotWalkable;
						++nonWalkableCount;

						continue;
					}

					size_t top = spaceTop;

					if (s + 1 < count)
					{
						const CompactSpanGrid::Span& nextSpan = m_spanGrid.GetSpan(cell.index + s + 1);
						top = nextSpan.bottom;
					}

					const size_t walkableHeight = top - (span.bottom + span.height);

					if (walkableHeight < heightVoxelCount)
					{
						span.flags |= NotWalkable;
						++nonWalkableCount;

						continue;
					}
				}
			}
		}

		// discard cliff edges
		const size_t NeighbourCount = 8;
		const size_t border = BorderSizeH();

		for (size_t y = 0; y < gridHeight; ++y)
		{
			const size_t ymult = y * gridWidth;

			for (size_t x = 0; x < gridWidth; ++x)
			{
				bool boundaryCell = IsBoundaryCell(x, y);

				if (const CompactSpanGrid::Cell cell = m_spanGrid[x + ymult])
				{
					size_t count = cell.count;

					for (size_t s = 0; s < count; ++s)
					{
						size_t index = cell.index + s;

						CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index);

						size_t flags = span.flags;
						flags |= boundaryCell ? TileBoundary : 0;

						if (flags & NotWalkable)
						{
							span.flags = flags;

							continue;
						}

						const size_t top = span.bottom + span.height;
						const size_t walkableHeight = (s + 1 < count) ? (m_spanGrid.GetSpan(index + 1).bottom - top) : spaceTop - top;

						size_t connMax = top;
						size_t connMin = top;

						size_t above = 0;
						size_t below = ~0ul;
						size_t connected = 0;
						size_t neighbours = 0;

						for (size_t n = 0; (n < NeighbourCount) && ((flags & NotWalkable) == 0); ++n)
						{
							size_t nx = x + NeighbourOffset_TileGenerator[n][0];
							size_t ny = y + NeighbourOffset_TileGenerator[n][1];

							const CompactSpanGrid::Cell ncell = m_spanGrid.GetCell(nx, ny);

							if (!ncell)
							{
								if ((nx < gridWidth) && (ny < gridHeight))
								{
									flags |= NotWalkable;

									continue;
								}
							}

							const size_t ncount = ncell.count;
							const size_t nindex = ncell.index;

							for (size_t ns = 0; ns < ncount; ++ns)
							{
								const size_t nsindex = nindex + ns;
								const CompactSpanGrid::Span& nspan = m_spanGrid.GetSpan(nsindex);

								const size_t nbot = nspan.bottom;
								const size_t ntop = nbot + nspan.height;
								const size_t nwalkableHeight = 
									(ns + 1 < ncount) ? (m_spanGrid.GetSpan(nsindex + 1).bottom - ntop) : spaceTop - ntop;

								const int overlappingHeight = std::min<int>(top + walkableHeight, ntop + nwalkableHeight) - max(top, ntop);
								if (overlappingHeight < 0)
									continue;

								++neighbours;

								if ((ntop > above) && (nbot < top + heightVoxelCount))
									above = ntop;

								if ((ntop < below) && (ntop + nwalkableHeight > top))
									below = ntop;

								const int dtop = ntop - top;

								// connected if heights overlap within climbable range
								if ((size_t)abs(dtop) <= climbableVoxelCount)
								{
									++connected;

									if (ntop > connMax)
										connMax = ntop;

									if (ntop < connMin)
										connMin = ntop;

									break;
								}
							}
						}

						// lower or upper neighbour not climbable - top or bottom of cliff
						const int dip = top - below; // negative will overflow
						const int climb = above - top; // negative will overflow

						if (dip > (int)climbableVoxelCount)
							flags |= NotWalkable;
						else if ((climb > (int)climbableVoxelCount) && (dip > 0))
							flags |= NotWalkable;
						else if ((connMax - connMin) > climbableVoxelCount) // connected min and max too far away - steep hill
							flags |= NotWalkable;

						// no connections or not all neighbours - lone span
						if (!connected || (neighbours < NeighbourCount))
							flags |= NotWalkable; // lone spans are un-walkable

						if ((flags & NotWalkable) != (span.flags & NotWalkable))
							++nonWalkableCount;

						span.flags = flags;
					}
				}
			}
		}
		
		// apply boundaries
		if (!fullyContained)
		{
			const float convX = 1.0f / m_params.voxelSize.x;
			const float convY = 1.0f / m_params.voxelSize.y;
			const float convZ = 1.0f / m_params.voxelSize.z;
		
			const Vec3 voxelSize = m_params.voxelSize;
			const Vec3 halfVoxel = m_params.voxelSize * 0.5f;

			const Vec3 bmax = aabb.max - aabb.min;

			for (size_t e = 0; e < m_params.exclusionCount; ++e)
			{
				const BoundingVolume& exclusion = m_params.exclusions[e];

				if (exclusion.Overlaps(aabb))
				{
					const Vec3 emin = (exclusion.aabb.min - aabb.min);
					const Vec3 emax = (exclusion.aabb.max - aabb.min);

					uint16 xmin = (uint16)(std::max(0.0f, emin.x) * convX);
					uint16 xmax = (uint16)(std::min(bmax.x, emax.x) * convX);

					uint16 ymin = (uint16)(std::max(0.0f, emin.y) * convY);
					uint16 ymax = (uint16)(std::min(bmax.y, emax.y) * convY);

					uint16 zmin = (uint16)(std::max(0.0f, emin.z) * convZ);
					uint16 zmax = (uint16)(std::min(bmax.z, emax.z) * convZ);

					for (uint16 y = ymin; y <= ymax; ++y)
					{
						const size_t ymult = y * gridWidth;

						for (uint16 x = xmin; x <= xmax; ++x)
						{
							if (const CompactSpanGrid::Cell& cell = m_spanGrid[x + ymult])
							{
								for (size_t s = 0; s < cell.count; ++s)
								{
									CompactSpanGrid::Span& span = m_spanGrid.GetSpan(cell.index + s);
									
									if (span.flags & NotWalkable)
										continue;

									size_t top = span.bottom + span.height;

									if ((top >= zmin) && (top <= zmax))
									{
										const Vec3 point = aabb.min + halfVoxel + Vec3(x * voxelSize.x, y * voxelSize.y, top * voxelSize.z);
										
										if (exclusion.Contains(point))
											span.flags |= NotWalkable;
									}
								}
							}
						}
					}
				}
			}

			if (m_params.boundary)
			{
				const BoundingVolume& boundary = *m_params.boundary;

				for (uint16 y = 0; y <= gridHeight; ++y)
				{
					const size_t ymult = y * gridWidth;

					for (uint16 x = 0; x <= gridWidth; ++x)
					{
						const CompactSpanGrid::Cell& cell = m_spanGrid[x + ymult];

						if (cell)
						{
							for (size_t s = 0; s < cell.count; ++s)
							{
								CompactSpanGrid::Span& span = m_spanGrid.GetSpan(cell.index + s);

								if (span.flags & NotWalkable)
									continue;

								size_t top = span.bottom + span.height;

								const Vec3 point = aabb.min + halfVoxel + Vec3(x * voxelSize.x, y * voxelSize.y, top * voxelSize.z);

								if (!boundary.Contains(point))
									span.flags |= NotWalkable;
							}
						}
					}
				}
			}
		}

		CompactSpanGrid compact;
		compact.CompactExcluding(m_spanGrid, NotWalkable, m_spanGrid.GetSpanCount() - nonWalkableCount);

		m_profiler.AddMemory(CompactSpanGridMemory, compact.GetMemoryUsage());

		compact.Swap(m_spanGrid);

		m_profiler.StopTimer(Filter);

		if (m_params.flags & Params::DebugInfo)
			m_spanGridFlagged.Swap(compact);
		else
			m_profiler.FreeMemory(CompactSpanGridMemory, compact.GetMemoryUsage());
	}

	inline bool IsBorderLabel(uint16 label)
	{
		return (label & (TileGenerator::BorderLabelH | TileGenerator::BorderLabelV)) != 0;
	}

	inline bool IsLabelValid(uint16 label)
	{
		return (label < TileGenerator::FirstInvalidLabel);
	}

/*	inline uint16 ConsolidateLabel(uint16 label)
	{
		if (label < TileGenerator::FirstInvalidLabel)
			return label;
		return TileGenerator::FirstInvalidLabel;
	}*/

	void TileGenerator::ComputeDistanceTransform()
	{
		m_profiler.StartTimer(DistanceTransform);

		const size_t gridWidth = m_spanGrid.GetWidth();
		const size_t gridHeight = m_spanGrid.GetHeight();
		const size_t gridSize = gridWidth * gridHeight;
		const size_t spanCount = m_spanGrid.GetSpanCount();

		const size_t climbableVoxelCount = m_params.agent.climbableHeight;

		m_distances.resize(spanCount);

		m_profiler.AddMemory(SegmentationMemory, m_distances.size() * sizeof(SpanExtraInfo::value_type));

		std::fill(m_distances.begin(), m_distances.end(), NoLabel);

		const size_t KStraight = 2;
		const size_t KDiagonal = 3;

		struct SweepElement
		{
			int x;
			int y;
			int k;
		};

		const size_t SweepPixelCount = 4;

		const SweepElement downSweep[SweepPixelCount] = 
		{
			{ -1, 0, KStraight },
			{ -1,-1, KDiagonal },
			{  0,-1, KStraight },
			{  1,-1, KDiagonal },
		};

		for (size_t y = 0; y < gridHeight; ++y)
		{
			for (size_t x = 0; x < gridWidth; ++x)
			{
				if (const CompactSpanGrid::Cell cell = m_spanGrid.GetCell(x, y))
				{
					size_t index = cell.index;
					size_t count = cell.count;

					for (size_t s = 0; s < count; ++s)
					{
						const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index + s);

						const size_t top = span.bottom + span.height;
						const uint16 current = m_distances[index + s];

						uint16 sweepValues[SweepPixelCount];

						for (size_t p = 0; p < SweepPixelCount; ++p)
						{
							sweepValues[p] = 0;

							const size_t nx = x + downSweep[p].x;
							const size_t ny = y + downSweep[p].y;

							size_t nindex;
							if (m_spanGrid.GetSpanAt(nx, ny, top, climbableVoxelCount, nindex))
								sweepValues[p] = m_distances[nindex] + downSweep[p].k;
						}

						uint16 minimum = sweepValues[0];

						for (size_t p = 1; p < SweepPixelCount; ++p)
							minimum = std::min<uint16>(minimum, sweepValues[p]);

						if (minimum < current)
							m_distances[index + s] = minimum;
					}
				}
			}
		}

		const SweepElement upSweep[SweepPixelCount] =
		{
			{ 1, 0, KStraight },
			{ 1, 1, KDiagonal },
			{ 0, 1, KStraight },
			{-1, 1, KDiagonal },
		};

		for (size_t y = gridHeight - 1; y; --y)
		{
			for (size_t x = gridWidth; x; --x)
			{
				if (const CompactSpanGrid::Cell cell = m_spanGrid.GetCell(x, y))
				{
					size_t index = cell.index;
					size_t count = cell.count;

					for (size_t s = 0; s < count; ++s)
					{
						const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index + s);

						const size_t top = span.bottom + span.height;
						const uint16 current = m_distances[index + s];

						uint16 sweepValues[SweepPixelCount];

						for (size_t p = 0; p < SweepPixelCount; ++p)
						{
							sweepValues[p] = 0;

							const size_t nx = x + upSweep[p].x;
							const size_t ny = y + upSweep[p].y;

							size_t nindex;
							if (m_spanGrid.GetSpanAt(nx, ny, top, climbableVoxelCount, nindex))
								sweepValues[p] = m_distances[nindex] + upSweep[p].k;
						}

						uint16 minimum = sweepValues[0];

						for (size_t p = 1; p < SweepPixelCount; ++p)
							minimum = std::min<uint16>(minimum, sweepValues[p]);

						if (minimum < current)
							m_distances[index + s] = minimum;
					}
				}
			}
		}

		m_profiler.StopTimer(DistanceTransform);
	}

	void TileGenerator::BlurDistanceTransform()
	{
		if (!m_params.blurAmount)
			return;

		m_profiler.StartTimer(Blur);

		const size_t threshold = 1;
		const size_t gridWidth = m_spanGrid.GetWidth();
		const size_t gridHeight = m_spanGrid.GetHeight();
		const size_t gridSize = gridWidth * gridHeight;
		const size_t spanCount = m_spanGrid.GetSpanCount();

		const size_t climbableVoxelCount = m_params.agent.climbableHeight;

		m_labels.resize(m_distances.size());

		for (size_t i = 0; i < m_params.blurAmount; ++i)
		{
			for (size_t y = 0; y < gridHeight; ++y)
			{
				for (size_t x = 0; x < gridWidth; ++x)
				{
					if (const CompactSpanGrid::Cell cell = m_spanGrid.GetCell(x, y))
					{
						size_t index = cell.index;
						size_t count = cell.count;

						for (size_t s = 0; s < count; ++s)
						{
							const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index + s);
							const size_t orig = m_distances[index + s];

							if (orig > threshold)
							{
								const size_t top = span.bottom + span.height;
								size_t accum = orig;

								for (size_t n = 0; n < 8; ++n)
								{
									const size_t nx = x + NeighbourOffset_TileGenerator[n][0];
									const size_t ny = y + NeighbourOffset_TileGenerator[n][1];

									size_t nindex;
									if (m_spanGrid.GetSpanAt(nx, ny, top, climbableVoxelCount, nindex))
										accum += m_distances[nindex];
									else
										accum += orig;
								}

								const size_t c = (accum + 5) / 9; // round
								m_labels[index + s] = c;
							}
							else
								m_labels[index + s] = orig;			
						}
					}
				}
			}

			if ((i & 1) == 0)
				m_labels.swap(m_distances);
		}

		m_profiler.StopTimer(Blur);
	}

	struct StreamElement
	{
		StreamElement(size_t _x, size_t _y, size_t _span)
			: x(_x)
			, y(_y)
			, span(_span)
		{
		}

		uint16 x;
		uint16 y;
		size_t span;

		bool operator==(const StreamElement& other) const
		{
			return (x == other.x) && (y == other.y) && (span == other.span);
		}

		bool operator<(const StreamElement& other) const
		{
			if (x == other.x)
			{
				if (y == other.y)
					return (span < other.span);
				return (y < other.y);
			}

			return x < other.x;
		}
	};


	typedef std::vector<StreamElement> LinearStream;

	size_t RunStream(const CompactSpanGrid& spanGrid, size_t climbableVoxelCount, LinearStream& unexplored, 
		const StreamElement& first, LinearStream& stream, const uint16* data, size_t erosion, uint16* labels)
	{
		stream.clear();
		stream.push_back(first);

		unexplored.clear();
		unexplored.push_back(first);

		while (!unexplored.empty())
		{
			const StreamElement y = unexplored.back();
			unexplored.pop_back();

			const size_t yx = y.x;
			const size_t yy = y.y;

			const CompactSpanGrid::Span& yspan = spanGrid.GetSpan(first.span);
			const size_t ytop = yspan.bottom + yspan.height;

			size_t minimum = erosion;
			bool bfirst = true;

			while (bfirst)
			{
				for (size_t n = 0; n < 4; ++n)
				{
					size_t nx = yx + NeighbourOffset_TileGenerator[n][0];
					size_t ny = yy + NeighbourOffset_TileGenerator[n][1];

					size_t nindex;
					if (spanGrid.GetSpanAt(nx, ny, ytop, climbableVoxelCount, nindex))
					{
						uint16 label = labels[nindex];

						if (!IsBorderLabel(label))
						{
							uint16 ndata = data[nindex];
							if (ndata > minimum)
								minimum = ndata;
						}
					}
				}

				size_t zx = ~0ul;
				size_t zy = ~0ul;
				size_t zspan = 0;

				for (size_t n = 0; n < 4; ++n)
				{
					const size_t nx = yx + NeighbourOffset_TileGenerator[n][0];
					const size_t ny = yy + NeighbourOffset_TileGenerator[n][1];

					size_t nindex;
					if (spanGrid.GetSpanAt(nx, ny, ytop, climbableVoxelCount, nindex))
					{
						uint16 label = labels[nindex];

						if (!IsBorderLabel(label))
						{
							uint16 ndata = data[nindex];

							if (data[nindex] == minimum)
							{
								const StreamElement probe(nx, ny, nindex);

								if (std::find(stream.begin(), stream.end(), probe) == stream.end())
								{
									zx = nx;
									zy = ny;
									zspan = nindex;
									break;
								}						
							}
						}
					}
				}

				if (zx == ~0ul)
					break;

				if (IsLabelValid(labels[zspan]))
					return labels[zspan];
				else
				{
					if (data[zspan] > data[y.span])
					{
						unexplored.clear();
						bfirst = false;
					}

					stream.push_back(StreamElement(zx, zy, zspan));
					unexplored.push_back(StreamElement(zx, zy, zspan));
				}
			}
		}

		return TileGenerator::NoLabel;
	}

	void TileGenerator::PaintBorder(uint16* data, size_t borderH, size_t borderV)
	{
		const size_t width = m_spanGrid.GetWidth();
		const size_t height = m_spanGrid.GetHeight();

		if (borderH)
		{
			for (size_t y = 0; y < height; ++y)
			{
				for (size_t b = 0; b < 2; ++b)
				{
					size_t xoffset = b * (width - borderH);

					for (size_t x = 0; x < borderH; ++x)
					{
						if (const CompactSpanGrid::Cell cell = m_spanGrid.GetCell(x + xoffset, y))
						{
							const size_t index = cell.index;
							const size_t count = cell.count;

							for (size_t s = 0; s < count; ++s)
								data[index + s] |= BorderLabelH;
						}
					}
				}
			}

			size_t hwidth = width - borderH;

			for (size_t b = 0; b < 2; ++b)
			{
				const size_t yoffset = b * (height - borderH);

				for (size_t y = 0; y < borderH; ++y)
				{
					for (size_t x = borderH; x < hwidth; ++x)
					{
						if (const CompactSpanGrid::Cell cell = m_spanGrid.GetCell(x, y + yoffset))
						{
							const size_t index = cell.index;
							const size_t count = cell.count;

							for (size_t s = 0; s < count; ++s)
								data[index + s] |= BorderLabelH;
						}
					}
				}
			}
		}

		if (borderV)
		{
			const size_t extraHeight = m_params.agent.height;
			const size_t maxTop = borderV + m_top;

			for (size_t y = 0; y < height; ++y)
			{
				for (size_t x = 0; x < width; ++x)
				{
					if (const CompactSpanGrid::Cell cell = m_spanGrid.GetCell(x, y))
					{
						const size_t index = cell.index;
						const size_t count = cell.count;

						for (size_t s = 0; s < count; ++s)
						{
							CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index + s);
							const uint16 top = span.bottom + span.height;

							if ((top < borderV) || (top >= maxTop))
								data[index + s] |= BorderLabelV;
						}
					}
				}
			}
		}
	}
	
	real_t DistVertexToLineSq(int x, int y, int ax, int ay, int bx, int by)
	{
		const vector3_t diff(x - ax, y - ay, 0);
		const vector3_t dir(bx - ax, by - ay, 0);
		const real_t t = diff.dot(dir);

		if (t > 0)
		{
			const real_t lenSq = dir.lenSq();

			if (t >= lenSq)
				return (diff - dir).lenSq();
			else
				return (diff - (dir * (t / lenSq))).lenSq();
		}

		return diff.lenSq();
	}

	real_t DistVertexToLineSq(int x, int y, int z, int ax, int ay, int az, int bx, int by, int bz)
	{
		const vector3_t diff(x - ax, y - ay, z - az);
		const vector3_t dir(bx - ax, by - ay, bz - az);
		const real_t t = diff.dot(dir);

		if (t > 0)
		{
			const real_t lenSq = dir.lenSq();
			
			if (t >= lenSq)
				return (diff - dir).lenSq();
			else
				return (diff - (dir * (t / lenSq))).lenSq();
		}

		return diff.lenSq();
	}

	const real_t AddContourVertexThreshold(real_t::fraction(15, 1000));

	void TileGenerator::AddContourVertex(const ContourVertex& contourVertex, Region& region, Contour& contour) const
	{
		if ((contour.size() < 2) || !ContourVertexRemovable(contour.back()))
			contour.push_back(contourVertex);
		else
		{
			ContourVertex& middle = contour.back();
			const ContourVertex& left = contour[contour.size() - 2];

			real_t distSq = DistVertexToLineSq(middle.x, middle.y, middle.z, left.x, left.y, left.z,
				contourVertex.x, contourVertex.y, contourVertex.z);
			
			if (distSq <= AddContourVertexThreshold)
				middle = contourVertex;
			else
				contour.push_back(contourVertex);
		}

		if (contourVertex.flags & ContourVertex::TileBoundary)
			region.flags |= Region::TileBoundary;

		if (contourVertex.flags & ContourVertex::TileBoundaryV)
			region.flags |= Region::TileBoundaryV;
	}

	bool TileGenerator::GatherSurroundingInfo(const Vec2i& vertex, const Vec2i& direction, const uint16 top,
		const uint16 climbableVoxelCount, size_t& height, SurroundingSpanInfo& left, SurroundingSpanInfo& front,
		SurroundingSpanInfo& frontLeft) const
	{
		Vec2i external = vertex + direction;
		bool result = false;

		height = top;

		size_t index;
		if (m_spanGrid.GetSpanAt(external.x, external.y, top, climbableVoxelCount, index))
		{
			const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index);
			maximize<size_t>(height, span.bottom + span.height);

			front.label = m_labels[index];
			front.flags = span.flags;
			front.index = index;
			result = true;
		}

		external = vertex + direction + direction.rot90ccw();
		if (m_spanGrid.GetSpanAt(external.x, external.y, top, climbableVoxelCount, index))
		{
			const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index);
			maximize<size_t>(height, span.bottom + span.height);

			frontLeft.label = m_labels[index];
			frontLeft.flags = span.flags;
			frontLeft.index = index;

			result = true;
		}

		external = vertex + direction.rot90ccw();
		if (m_spanGrid.GetSpanAt(external.x, external.y, top, climbableVoxelCount, index))
		{
			const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index);
			maximize<size_t>(height, span.bottom + span.height);

			left.label = m_labels[index];
			left.flags = span.flags;
			left.index = index;
			result = true;
		}

		return result;
	}

	void TileGenerator::DetermineContourVertex(const Vec2i& vertex, const Vec2i& direction, const uint16 top,
		const uint16 climbableVoxelCount, ContourVertex& contourVertex) const
	{
		size_t xoffs = (direction.x == 1) | (direction.y == -1);
		size_t yoffs = (direction.y == 1) | (direction.x == 1);

		size_t cx = vertex.x + xoffs;
		size_t cy = vertex.y + yoffs;
		size_t cz = top;

		bool internalBorderV = false;
		{
			size_t index;
			if (m_spanGrid.GetSpanAt(vertex.x, vertex.y, top, climbableVoxelCount, index))
				internalBorderV = (m_labels[index] & BorderLabelV) != 0;
		}

		assert((top >= BorderSizeV()) || internalBorderV);

		SurroundingSpanInfo front(NoLabel, ~0ul, NotWalkable);
		SurroundingSpanInfo frontLeft(NoLabel, ~0ul, NotWalkable);
		SurroundingSpanInfo left(NoLabel, ~0ul, NotWalkable);

		const size_t borderV = BorderSizeV();
		GatherSurroundingInfo(vertex, direction, top, climbableVoxelCount, cz, left, front, frontLeft);
		minimize(cz, borderV + m_top);

		size_t frontierCount = 0;
		size_t flags = 0;

		const size_t erosion = m_params.flags & Params::NoErosion ? 0 : m_params.agent.radius * 2;

		size_t walkableBit = 0;
		walkableBit = (((frontLeft.flags & NotWalkable) == 0) && (m_distances[frontLeft.index] >= erosion)) ? 1 : 0;
		walkableBit |= ((((left.flags & NotWalkable) == 0) && (m_distances[left.index] >= erosion)) ? 1 : 0) << 1;
		walkableBit |= ((((front.flags & NotWalkable) == 0) && (m_distances[front.index] >= erosion)) ? 1 : 0) << 2;

		size_t borderBitH = 0;
		borderBitH = (frontLeft.label & BorderLabelH) ? 1 : 0;
		borderBitH |= ((left.label & BorderLabelH) ? 1 : 0) << 1;
		borderBitH |= ((front.label & BorderLabelH) ? 1 : 0) << 2;

		size_t borderBitV = 0;
		borderBitV = (frontLeft.label & BorderLabelV) ? 1 : 0;
		borderBitV |= ((left.label & BorderLabelV) ? 1 : 0) << 1;
		borderBitV |= ((front.label & BorderLabelV) ? 1 : 0) << 2;

		const size_t borderBit = borderBitH | borderBitV;

		NeighbourClassification lclass = ClassifyNeighbour(left, erosion, BorderLabelV | BorderLabelH);
		NeighbourClassification flclass = ClassifyNeighbour(frontLeft, erosion, BorderLabelV | BorderLabelH);
		NeighbourClassification fclass = ClassifyNeighbour(front, erosion, BorderLabelV | BorderLabelH);

		// horizontal border
		{
			if (IsCornerVertex(cx, cy))
				flags |= ContourVertex::TileBoundary;
			else
			{
				const bool boundary = IsBoundaryVertex(cx, cy);

				if (boundary)
				{
					const bool frontBoundary = IsBoundaryCell(vertex.x + direction.x, vertex.y + direction.y)
						|| IsBorderCell(vertex.x + direction.x, vertex.y + direction.y);
					const bool connection = (borderBitH == 7) && walkableBit;

					if (frontBoundary && connection)
						flags |= ContourVertex::TileBoundary;

					if (CornerTable[lclass][flclass][fclass] || ((borderBit == 7) && (borderBitH && borderBitV)))
						flags |= ContourVertex::Unremovable;
				}
			}
		}

		// vertical border
		{
			if (borderBitV || internalBorderV)
			{
				flags |= ContourVertex::TileBoundaryV;

				if (!internalBorderV)
				{
					if (CornerTable[lclass][flclass][fclass] || ((borderBit == 7) && (borderBitH && borderBitV)))
						flags |= ContourVertex::Unremovable;
				}
			}

			if (flags & ContourVertex::TileBoundaryV)
			{
				if (cz < borderV + m_top)
					cz = borderV;
			}
		}

		contourVertex.x = cx;
		contourVertex.y = cy;
		contourVertex.z = cz;
		contourVertex.flags = flags;
	}

	inline bool IsWalkable(uint16 label, uint16 distance,	size_t erosion)
	{
		if ((label & (TileGenerator::BorderLabelH | TileGenerator::BorderLabelV)) != 0)
			return false;

		if (distance < erosion)
			return false;

		return true;
	}

	inline bool IsWalkable(const Vec2i& voxel, size_t& index, uint16& label, size_t top, size_t climbableVoxelCount,
		size_t erosion,	const CompactSpanGrid& spanGrid, const uint16* distances, const uint16* labels)
	{
		if (!spanGrid.GetSpanAt(voxel.x, voxel.y, top, climbableVoxelCount, index))
			return false;

		label = labels[index];
		if ((label & (TileGenerator::BorderLabelH | TileGenerator::BorderLabelV)) != 0)
			return false;

		if (distances[index] < erosion)
			return false;

		return true;
	}

	void TileGenerator::TraceExternalContour(size_t x, size_t y, size_t top, size_t erosion,
		size_t climbableVoxelCount, uint16 label, Region& region)
	{
		Vec2i start(x, y);
		Vec2i current(start);
		Vec2i last(start);

		Vec2i direction(-1, 0);
		Vec2i startdirection(direction);

		size_t rotationCount = 0;

		Contour& contour = region.contour;
		contour.reserve(512);

		for ( ; ((current != start) || (direction != startdirection)) || contour.empty(); )
		{
			if (contour.size() >= 2048)
				break;

			Vec2i front = current + direction;
			Vec2i left = front + direction.rot90ccw();
			Vec2i right = front + direction.rot90cw();

			size_t lindex = ~0ul;
			uint16 llabel = NoLabel;

			size_t findex = ~0ul;
			uint16 flabel = NoLabel;

			size_t rindex = ~0ul;
			uint16 rlabel = NoLabel;

			bool lwalkable = IsWalkable(left, lindex, llabel, top, climbableVoxelCount, erosion, m_spanGrid, &m_distances[0], &m_labels[0]);
			bool fwalkable = IsWalkable(front, findex, flabel, top, climbableVoxelCount, erosion, m_spanGrid, &m_distances[0], &m_labels[0]);
			bool rwalkable = IsWalkable(right, rindex, rlabel, top, climbableVoxelCount, erosion, m_spanGrid, &m_distances[0], &m_labels[0]);

			if (lwalkable)
			{
				direction = direction.rot90ccw();
				current = left;

				const CompactSpanGrid::Span& currentSpan = m_spanGrid.GetSpan(lindex);
				top = currentSpan.bottom + currentSpan.height;

				m_labels[lindex] = label;
				++region.spanCount;
			}
			else if (fwalkable)
			{
				if ((lindex != ~0ul) && !lwalkable)
					m_labels[lindex] = llabel | ExternalContour;

				m_labels[findex] = label;
				++region.spanCount;

				const CompactSpanGrid::Span& currentSpan = m_spanGrid.GetSpan(findex);
				top = currentSpan.bottom + currentSpan.height;

				current = front;
			}
			else if (rwalkable)
			{
				if ((lindex != ~0ul) && !lwalkable)
					m_labels[lindex] = llabel | ExternalContour;

				if ((findex != ~0ul) && !fwalkable)
					m_labels[findex] = flabel | ExternalContour;

				m_labels[rindex] = label;
				++region.spanCount;

				// right turns need an extra vertex
				ContourVertex vertex;
				DetermineContourVertex(last, direction.rot90cw(), top, climbableVoxelCount,	vertex);
				AddContourVertex(vertex, region, contour);

				const CompactSpanGrid::Span& currentSpan = m_spanGrid.GetSpan(rindex);
				top = currentSpan.bottom + currentSpan.height;

				current = right;
			}
			else if (rotationCount >= 3)
				break;
			else
			{
				++rotationCount;
				direction = direction.rot90cw();

				if ((lindex != ~0ul) && !lwalkable)
					m_labels[lindex] = llabel | ExternalContour;

				if ((findex != ~0ul) && !fwalkable)
					m_labels[findex] = flabel | ExternalContour;

				if ((rindex != ~0ul) && !rwalkable)
					m_labels[rindex] = rlabel | ExternalContour;

				ContourVertex vertex;
				DetermineContourVertex(last, direction, top, climbableVoxelCount, vertex);
				AddContourVertex(vertex, region, contour);

				continue;
			}

			if (contour.empty())
				startdirection = direction;

			last = current;
			rotationCount = 0;

			ContourVertex vertex;
			DetermineContourVertex(current, direction, top, climbableVoxelCount, vertex);
			AddContourVertex(vertex, region, contour);
		}

		TidyUpContourEnd(contour);
	}

	void TileGenerator::TraceInternalContour(size_t x, size_t y, size_t top, size_t erosion, 
		size_t climbableVoxelCount, uint16 label, Region& region)
	{
		Vec2i start(x, y);
		Vec2i current(start);
		Vec2i last(start);

		Vec2i direction(-1, 0);
		Vec2i startdirection(direction);

		size_t rotationCount = 0;

		Contour& contour = region.holes.back();
		contour.reserve(256);

		for ( ; ((current != start) || (direction != startdirection)) || contour.empty(); )
		{
			if (contour.size() >= 2048)
				break;

			Vec2i front = current + direction;
			Vec2i left = front + direction.rot90ccw();
			Vec2i right = front + direction.rot90cw();

			size_t lindex = ~0ul;
			uint16 llabel = NoLabel;

			size_t findex = ~0ul;
			uint16 flabel = NoLabel;

			size_t rindex = ~0ul;
			uint16 rlabel = NoLabel;

			bool lwalkable = IsWalkable(left, lindex, llabel, top, climbableVoxelCount, erosion, m_spanGrid, &m_distances[0], &m_labels[0]);
			bool fwalkable = IsWalkable(front, findex, flabel, top, climbableVoxelCount, erosion, m_spanGrid, &m_distances[0], &m_labels[0]);
			bool rwalkable = IsWalkable(right, rindex, rlabel, top, climbableVoxelCount, erosion, m_spanGrid, &m_distances[0], &m_labels[0]);

			if (!lwalkable && ((llabel & ExternalContour) == 0))
			{
				direction = direction.rot90ccw();
				current = left;

				const CompactSpanGrid::Span& currentSpan = m_spanGrid.GetSpan(lindex);
				top = currentSpan.bottom + currentSpan.height;

				m_labels[lindex] |= InternalContour;
			}
			else if (!fwalkable && ((rlabel & ExternalContour) == 0))
			{
				if ((lindex != ~0ul) && lwalkable)
					m_labels[lindex] = label;

				m_labels[findex] |= InternalContour;

				const CompactSpanGrid::Span& currentSpan = m_spanGrid.GetSpan(findex);
				top = currentSpan.bottom + currentSpan.height;

				current = front;
			}
			else if (!rwalkable && ((rlabel & ExternalContour) == 0))
			{
				if ((lindex != ~0ul) && lwalkable)
					m_labels[lindex] = label;

				if ((findex != ~0ul) && fwalkable)
					m_labels[findex] = label;

				m_labels[rindex] |= InternalContour;

				// right turns need an extra vertex
				ContourVertex vertex;
				DetermineContourVertex(last, direction.rot90cw(), top, climbableVoxelCount,	vertex);
				AddContourVertex(vertex, region, contour);

				const CompactSpanGrid::Span& currentSpan = m_spanGrid.GetSpan(rindex);
				top = currentSpan.bottom + currentSpan.height;

				current = right;
			}
			else if (rotationCount >= 3)
				break;
			else
			{
				++rotationCount;
				direction = direction.rot90cw();

				if ((lindex != ~0ul) && lwalkable)
					m_labels[lindex] = label;

				if ((findex != ~0ul) && fwalkable)
					m_labels[findex] = label;

				if ((rindex != ~0ul) && rwalkable)
					m_labels[rindex] = label;

				ContourVertex vertex;
				DetermineContourVertex(last, direction, top, climbableVoxelCount, vertex);
				AddContourVertex(vertex, region, contour);

				continue;
			}

			if (contour.empty())
				startdirection = direction;

			last = current;
			rotationCount = 0;

			ContourVertex vertex;
			DetermineContourVertex(current, direction, top, climbableVoxelCount, vertex);
			AddContourVertex(vertex, region, contour);
		}

		TidyUpContourEnd(contour);
	}

	void TileGenerator::TidyUpContourEnd(Contour& contour)
	{
		if (contour.size() > 2)
		{
			const ContourVertex& left = contour[contour.size() - 2];
			const ContourVertex& middle = contour.back();
			const ContourVertex& right = contour.front();

			if ((DistVertexToLineSq(middle.x, middle.y, middle.z, left.x, left.y, left.z, 
				right.x, right.y, right.z) <= AddContourVertexThreshold) && ContourVertexRemovable(middle))
				contour.pop_back();
		}

		if (contour.size() > 2)
		{
			const ContourVertex& left = contour.back();
			ContourVertex& middle = contour.front();
			const ContourVertex& right = contour[1];

			if ((DistVertexToLineSq(middle.x, middle.y, middle.z, left.x, left.y, left.z, 
				right.x, right.y, right.z) <= AddContourVertexThreshold) && ContourVertexRemovable(middle))
			{
				middle = left;
				contour.pop_back();
			}
		}
	}

	size_t TileGenerator::ExtractContours()
	{
		m_profiler.StartTimer(ContourExtraction);

		const size_t gridWidth = m_spanGrid.GetWidth();
		const size_t gridHeight = m_spanGrid.GetHeight();
		const size_t gridSize = gridWidth * gridHeight;
		const size_t spanCount = m_spanGrid.GetSpanCount();

		m_labels.resize(m_distances.size());

		m_profiler.AddMemory(SegmentationMemory, m_labels.size() * sizeof(SpanExtraInfo::value_type));

		const size_t borderH = BorderSizeH();
		const size_t borderV = BorderSizeV();

		std::fill(m_labels.begin(), m_labels.end(), NoLabel);
		PaintBorder(&m_labels.front(), borderH, borderV);

		size_t regionCount = 0;
		m_regions.reserve(128);

		const size_t erosion = m_params.flags & Params::NoErosion ? 0 : m_params.agent.radius << 1;
		const size_t climbableVoxelCount = m_params.agent.climbableHeight;

		for (size_t y = borderH; y < gridHeight - borderH; ++y)
		{
			for (size_t x = borderH; x < gridWidth - borderH; ++x)
			{
				if (const CompactSpanGrid::Cell cell = m_spanGrid.GetCell(x, y))
				{
					const size_t cindex = cell.index;
					const size_t ccount = cell.count;

					for (size_t s = 0; s < ccount; ++s)
					{
						const size_t index = cindex + s;
						const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index);
						const size_t top = span.bottom + span.height;

						uint16 label = m_labels[index];

						if ((label & ExternalContour) || (label & InternalContour))
							continue;

						bool walkable = IsWalkable(label, m_distances[index], erosion);

						size_t pindex;
						uint16 plabel = NoLabel;
						bool pwalkable = IsWalkable(Vec2i(x - 1, y), pindex, plabel, top, climbableVoxelCount, erosion,
							m_spanGrid, &m_distances[0], &m_labels[0]);

						if (walkable && (label == NoLabel))
						{
							if (pwalkable)
							{
								assert(plabel != NoLabel);

								m_labels[index] = plabel;

								Region& region = m_regions[plabel];
								++region.spanCount;
							}
							else
							{
								label = regionCount;
								m_regions.resize(++regionCount);

								Region& region = m_regions.back();

								m_labels[index] = label;
								TraceExternalContour(x, y, top, erosion, climbableVoxelCount, label, region);
							}
						}
						else if (!walkable && pwalkable)
						{
							assert(plabel != NoLabel);

							Region& region = m_regions[plabel];
							region.holes.reserve(64);
							region.holes.resize(region.holes.size() + 1);

							TraceInternalContour(x, y, top, erosion, climbableVoxelCount, plabel, region);
						}
					}
				}
			}
		}

		m_profiler.StopTimer(ContourExtraction);

		m_profiler.AddMemory(RegionMemory, m_regions.capacity() * sizeof(Region));

		for (size_t i = 0; i < m_regions.size(); ++i)
		{
			const Region& region = m_regions[i];

			size_t memory = region.contour.capacity() * sizeof(ContourVertex);
			memory += region.holes.capacity() * sizeof(Contour);

			for (size_t h = 0; h < region.holes.size(); ++h)
				memory += region.holes[h].capacity() * sizeof(ContourVertex);

			m_profiler.AddMemory(RegionMemory, memory);
		}

		if ((m_params.flags & Params::DebugInfo) == 0)
		{
			SpanExtraInfo().swap(m_labels);

			m_profiler.FreeMemory(SegmentationMemory, m_labels.capacity() * sizeof(SpanExtraInfo::value_type));

			SpanExtraInfo().swap(m_distances);

			m_profiler.FreeMemory(SegmentationMemory, m_distances.capacity() * sizeof(SpanExtraInfo::value_type));
		}

		return regionCount;
	}

	size_t TileGenerator::InsertUniqueVertex(VertexIndexLookUp& lookUp, size_t x, size_t y, size_t z)
	{
		enum { zmask = (1 << 11) - 1,	};
		enum { xmask = (1 << 10) - 1,	};
		enum { ymask = (1 << 10) - 1,	};

		const uint32 vertexID = ((uint32)(z & zmask) << 20) | ((x & xmask) << 10) | (y & ymask);

		bool inserted;
		uint16& index = *lookUp.insert(vertexID, 0, &inserted);

		if (inserted)
		{
			index = m_vertices.size();

			m_vertices.push_back(Tile::Vertex(
				Tile::Vertex::value_type(x * m_params.voxelSize.x),
				Tile::Vertex::value_type(y * m_params.voxelSize.y),
				Tile::Vertex::value_type(z * m_params.voxelSize.z)));
		}

		return index;
	}

	void TileGenerator::FilterBadRegions(size_t minSpanCount)
	{
		for (size_t i = 0; i < m_regions.size(); ++i)
		{
			Region& region = m_regions[i];

			if (((region.flags & Region::TileBoundary) == 0)
				&& ((region.flags & Region::TileBoundaryV) == 0)
				&& (region.spanCount && (region.spanCount <= minSpanCount)))
			{
				Region().swap(region);
			}
		}
	}

	bool TileGenerator::SimplifyContour(const Contour& contour, const real_t& tolerance2DSq,
		const real_t& tolerance3DSq, PolygonContour& poly)
	{
		const size_t MaxSimplifiedCount = 2048;
		uint16 simplified[MaxSimplifiedCount];
		size_t simplifiedCount = 0;

		bool boundary = (contour.back().flags & ContourVertex::TileBoundaryV) != 0;

		for (size_t i = 0; i < contour.size(); ++i)
		{
			const ContourVertex& v = contour[i];

			if (v.flags & ContourVertex::TileBoundaryV)
			{
				if (!boundary || !ContourVertexRemovable(v))
					simplified[simplifiedCount++] = i;

				boundary = true;
			}
			else
			{
				if (boundary && i && (simplified[simplifiedCount - 1] != (i - 1)))
					simplified[simplifiedCount++] = i - 1;

				if (!ContourVertexRemovable(v))
					simplified[simplifiedCount++] = i;

				boundary = false;
			}
		}

		if (simplifiedCount && (simplified[simplifiedCount - 1] != (contour.size() - 1)))
		{
			if ((contour.back().flags & ContourVertex::TileBoundaryV)
				&& ((contour.front().flags & ContourVertex::TileBoundaryV) == 0))
			{
				simplified[simplifiedCount++] = (contour.size() - 1);
			}
		}

		if (!simplifiedCount)
		{
			Vec3i min(std::numeric_limits<int>::max());
			size_t minVertex = 0;

			Vec3i max(std::numeric_limits<int>::min());
			size_t maxVertex = 0;

			for (size_t i = 0; i < contour.size(); ++i)
			{
				const ContourVertex& v = contour[i];

				if ((v.x < min.x) || ((v.x == min.x) && (v.y > min.y)))
				{
					minVertex = i;
					min = Vec3i(v.x, v.y, v.z);
				}

				if ((v.x > max.x) || ((v.x == max.x) && (v.y > min.y)))
				{
					maxVertex = i;
					max = Vec3i(v.x, v.y, v.z);
				}
			}

			simplified[simplifiedCount++] = minVertex;
			simplified[simplifiedCount++] = maxVertex;
		}

		const size_t contourSize = contour.size();

		for (size_t s0 = 0; s0 < simplifiedCount; )
		{
			const size_t s1 = (s0 + 1) % simplifiedCount;
			const size_t i0 = simplified[s0];
			const size_t i1 = simplified[s1];
			const size_t last = (i0 < i1) ? i1 : contourSize + i1;

			const ContourVertex& v0 = contour[i0];
			const ContourVertex& v1 = contour[i1];

			real_t dmax2DSq = real_t::min();
			real_t dmax3DSq = real_t::min();
			size_t index2D = 0;
			size_t index3D = 0;

			if (v0 < v1)
			{
				for (size_t v = i0 + 1; v < last; ++v)
				{
					const size_t vi = v % contourSize;
					const ContourVertex& vp = contour[vi];
					const real_t d3DSq = DistVertexToLineSq(vp.x, vp.y, vp.z, v0.x, v0.y, v0.z, v1.x, v1.y, v1.z);
					const real_t d2DSq = DistVertexToLineSq(vp.x, vp.y, v0.x, v0.y, v1.x, v1.y);

					if (d2DSq > dmax2DSq)
					{
						index2D = vi;
						dmax2DSq = d2DSq;
					}

					if (d3DSq > dmax3DSq)
					{
						index3D = vi;
						dmax3DSq = d3DSq;
					}
				}
			}
			else
			{
				for (size_t v = last - 1; v > i0; --v)
				{
					const size_t vi = v % contourSize;
					const ContourVertex& vp = contour[vi];
					const real_t d3DSq = DistVertexToLineSq(vp.x, vp.y, vp.z, v0.x, v0.y, v0.z, v1.x, v1.y, v1.z);
					const real_t d2DSq = DistVertexToLineSq(vp.x, vp.y, v0.x, v0.y, v1.x, v1.y);

					if (d2DSq > dmax2DSq)
					{
						index2D = vi;
						dmax2DSq = d2DSq;
					}

					if (d3DSq > dmax3DSq)
					{
						index3D = vi;
						dmax3DSq = d3DSq;
					}
				}
			}

			size_t index = (dmax3DSq >= tolerance3DSq) ? index3D : ((dmax2DSq >= tolerance2DSq) ? index2D : ~0ul);

			if (index != ~0ul)
			{
				assert(simplifiedCount + 1 < MaxSimplifiedCount);
				if (simplifiedCount + 1 == MaxSimplifiedCount)
					break;

				for (size_t k = 0, i = s0 + 1; i < simplifiedCount; ++i, ++k)
					simplified[simplifiedCount - k] = simplified[simplifiedCount - k - 1];

				simplified[s0 + 1] = index3D;
				++simplifiedCount;

				continue;;
			}

			++s0;
		}

		if (simplifiedCount > 2)
		{
			PolygonContour spoly;
			spoly.reserve(simplifiedCount);

			for (size_t i = 0; i < simplifiedCount; ++i)
			{
				const ContourVertex& cv = contour[simplified[i]];
				spoly.push_back(PolygonVertex(cv.x, cv.y, cv.z));
			}

			poly.swap(spoly);

			return true;
		}

		return false;
	}

	void TileGenerator::SimplifyContours()
	{
		m_profiler.StartTimer(Simplification);

		const real_t tolerance2DSq(7);
		const real_t tolerance3DSq(11);

		size_t polygonCount = 0;

		for (size_t r = 0; r < m_regions.size(); ++r)
		{
			const Region& region = m_regions[r];
			polygonCount += (region.spanCount > 0);
		}

		m_polygons.reserve(polygonCount);

		for (size_t r = 0; r < m_regions.size(); ++r)
		{
			Region& region = m_regions[r];
			const Contour& contour = region.contour;

			if (contour.size() < 3)
				continue;

			m_polygons.resize(m_polygons.size() + 1);
			Polygon& poly = m_polygons.back();
			
			if (!SimplifyContour(region.contour, tolerance2DSq, tolerance3DSq, poly.contour))
			{
				m_polygons.pop_back();
				continue;
			}

			if (region.holes.empty())
				continue;

			poly.holes.reserve(region.holes.size());

			for (size_t h = 0; h < region.holes.size(); ++h)
			{
				poly.holes.resize(poly.holes.size() + 1);
				PolygonContour& hole = poly.holes.back();

				if (!SimplifyContour(region.holes[h], tolerance2DSq, tolerance3DSq, hole))
					poly.holes.pop_back();
			}
		}

		m_profiler.StopTimer(Simplification);

		m_profiler.AddMemory(PolygonMemory, m_polygons.capacity() * sizeof(Polygon));

		for (size_t i = 0; i < m_polygons.size(); ++i)
		{
			m_profiler.AddMemory(PolygonMemory, m_polygons[i].contour.capacity() * sizeof(PolygonContour::value_type));
			m_profiler.AddMemory(PolygonMemory, m_polygons[i].holes.capacity() * sizeof(PolygonHoles::value_type));

			for (size_t k = 0; k < m_polygons[i].holes.size(); ++k)
				m_profiler.AddMemory(PolygonMemory, m_polygons[i].holes[k].capacity() * sizeof(PolygonContour::value_type));
		}

		if ((m_params.flags & Params::DebugInfo) == 0)
		{
			Regions().swap(m_regions);

			m_profiler.FreeMemory(RegionMemory, m_profiler[RegionMemory].used);
		}

		m_profiler.AddStat(PolygonCount, m_polygons.size());
	}

	template<typename VertexTy>
	inline bool IsReflex(size_t vertex, const VertexTy* vertices, size_t vertexCount)
	{
		const uint16 i0 = vertex ? vertex - 1 : vertexCount - 1;
		const uint16 i1 = vertex;
		const uint16 i2 = (vertex + 1) % vertexCount;

		const VertexTy& v0 = vertices[i0];
		const VertexTy& v1 = vertices[i1];
		const VertexTy& v2 = vertices[i2];

		int area = ((int)v1.x - (int)v0.x) * ((int)v2.y - (int)v0.y) - ((int)v1.y - (int)v0.y) * ((int)v2.x - (int)v0.x);
		return area > 0;
	}

	template<typename VertexTy>
	inline bool IsReflex(size_t vertex, const VertexTy* vertices, uint16* indices, size_t indexCount)
	{
		const uint16 i0 = vertex ? vertex - 1 : indexCount - 1;
		const uint16 i1 = vertex;
		const uint16 i2 = (vertex + 1) % indexCount;

		const VertexTy& v0 = vertices[indices[i0]];
		const VertexTy& v1 = vertices[indices[i1]];
		const VertexTy& v2 = vertices[indices[i2]];

		int area = ((int)v1.x - (int)v0.x) * ((int)v2.y - (int)v0.y) - ((int)v1.y - (int)v0.y) * ((int)v2.x - (int)v0.x);
		return area > 0;
	}

	template<typename VertexTy>
	bool IsEar(size_t vertex, const VertexTy* vertices, size_t vertexCount, size_t agentHeight)
	{
		const uint16 i0 = vertex ? vertex - 1 : vertexCount - 1;
		const uint16 i1 = vertex;
		const uint16 i2 = (vertex + 1) % vertexCount;

		const VertexTy& v0 = vertices[i0];
		const VertexTy& v1 = vertices[i1];
		const VertexTy& v2 = vertices[i2];

		const size_t minZ = std::min<size_t>(std::min<size_t>(v0.z, v1.z), v2.z);
		const size_t maxZ = std::max<size_t>(std::max<size_t>(v0.z, v1.z), v2.z);

		for (size_t k = 0; k < vertexCount; ++k)
		{
			const VertexTy& cv = vertices[k];
			const Vec3i p(cv.x, cv.y, cv.z);

			if ((static_cast<size_t>(p.z) > maxZ + agentHeight) || (static_cast<size_t>(p.z) + agentHeight < minZ))
				continue;

			bool e0 = ((((int)p.x - (int)v0.x) * ((int)v0.y - (int)v1.y) - ((int)p.y - (int)v0.y) * ((int)v0.x - (int)v1.x)) < 0);
			bool e1 = ((((int)p.x - (int)v1.x) * ((int)v1.y - (int)v2.y) - ((int)p.y - (int)v1.y) * ((int)v1.x - (int)v2.x)) < 0);
			bool e2 = ((((int)p.x - (int)v2.x) * ((int)v2.y - (int)v0.y) - ((int)p.y - (int)v2.y) * ((int)v2.x - (int)v0.x)) < 0);

			if (e0 && e1 && e2)
				return false;
		}

		return true;
	}

	template<typename VertexTy>
	bool IsEar(size_t vertex, const VertexTy* vertices, size_t vertexCount, uint16* indices, size_t indexCount,
		size_t agentHeight)
	{
		const uint16 i0 = vertex ? vertex - 1 : indexCount - 1;
		const uint16 i1 = vertex;
		const uint16 i2 = (vertex + 1) % indexCount;

		const VertexTy& v0 = vertices[indices[i0]];
		const VertexTy& v1 = vertices[indices[i1]];
		const VertexTy& v2 = vertices[indices[i2]];

		const size_t minZ = std::min<size_t>(std::min<size_t>(v0.z, v1.z), v2.z);
		const size_t maxZ = std::max<size_t>(std::max<size_t>(v0.z, v1.z), v2.z);

		for (size_t k = 0 ; k < vertexCount; ++k)
		{
			const VertexTy& cv = vertices[k];
			const Vec3i p(cv.x, cv.y, cv.z);

			if ((static_cast<size_t>(p.z) > maxZ + agentHeight) || (static_cast<size_t>(p.z) + agentHeight < minZ))
				continue;

			bool e0 = ((((int)p.x - (int)v0.x) * ((int)v0.y - (int)v1.y) - ((int)p.y - (int)v0.y) * ((int)v0.x - (int)v1.x)) < 0);
			bool e1 = ((((int)p.x - (int)v1.x) * ((int)v1.y - (int)v2.y) - ((int)p.y - (int)v1.y) * ((int)v1.x - (int)v2.x)) < 0);
			bool e2 = ((((int)p.x - (int)v2.x) * ((int)v2.y - (int)v0.y) - ((int)p.y - (int)v2.y) * ((int)v2.x - (int)v0.x)) < 0);

			if (e0 && e1 && e2)
				return false;
		}

		return true;
	}

	size_t TileGenerator::Triangulate(PolygonContour& contour, const size_t agentHeight, const size_t borderH,
		const size_t borderV, VertexIndexLookUp& lookUp)
	{
		size_t triCount = 0;
		size_t vertexCount = contour.size();

		const size_t MaxIndices = 4096;
		uint16 indices[MaxIndices];

		for (size_t i = 0; i < vertexCount; ++i)
			indices[i] = i;		

		while (true)
		{
			size_t bestInsideCount = ~0ul;
			size_t bestDiagonalIdx = ~0ul;
			size_t bestDiagonalSq = ~0ul;

			size_t bestDelaugnayIdx = ~0ul;
			size_t bestDelaugnaySq = ~0ul;

			size_t ii = vertexCount - 1;

			for (size_t i = 0; i < vertexCount; ++i)
			{
				uint16 ii0 = ii;
				uint16 i0 = indices[ii];			
				uint16 i1 = indices[i];
				ii = i;

				const PolygonVertex& v1 = contour[i1];

				if ((v1.flags & PolygonVertex::Ear) == 0)
					continue;

				uint16 i2 = indices[(i + 1) % vertexCount];				

				const PolygonVertex& v0 = contour[i0];
				const PolygonVertex& v2 = contour[i2];
				
				const size_t minZ = std::min<size_t>(std::min<size_t>(v0.z, v1.z), v2.z);
				const size_t maxZ = std::max<size_t>(std::max<size_t>(v0.z, v1.z), v2.z);

				size_t insideCircumcircleCount = 0;

				size_t k = 0;
				for ( ; k < vertexCount - 3; ++k)
				{
					const PolygonVertex& cv = contour[indices[(ii0 + 3 + k) % vertexCount]];
					const Vec3i p(cv.x, cv.y, cv.z);

					if ((static_cast<size_t>(p.z) > maxZ + agentHeight) || (static_cast<size_t>(p.z) + agentHeight < minZ))
						continue;

					const int x13 = v0.x - v1.x;
					const int y13 = v0.y - v1.y;
					const int x23 = v2.x - v1.x;
					const int y23 = v2.y - v1.y;
					const int x1p = v0.x - p.x;
					const int y1p = v0.y - p.y;
					const int x2p = v2.x - p.x;
					const int y2p = v2.y - p.y;

					if (((x13 * x23 + y13 * y23) * (x2p * y1p - x1p * y2p)) < ((y13 * x23 - x13 * y23) * (x2p * x1p + y1p * y2p)))
						++insideCircumcircleCount;
				}

				if (k == (vertexCount - 3))
				{
					size_t diagonalSq = sqr(v2.x - v0.x) + sqr(v2.y - v0.y) + sqr(5 * (v2.z - v0.z));

					if (insideCircumcircleCount < bestInsideCount)
					{
						bestInsideCount = insideCircumcircleCount;
						bestDiagonalSq = diagonalSq;
						bestDiagonalIdx = i;
					}
					else if (insideCircumcircleCount == bestInsideCount)
					{
						if (diagonalSq < bestDiagonalSq)
						{
							bestDiagonalSq = diagonalSq;
							bestDiagonalIdx = i;
						}
					}

					if (insideCircumcircleCount == 0)
					{
						if (diagonalSq < bestDelaugnaySq)
						{
							bestDelaugnaySq = diagonalSq;
							bestDelaugnayIdx = i;
						}
					}
				}
			}

			size_t bestIdx = bestDelaugnayIdx;

			if (bestIdx == ~0ul)
			{
				bestIdx = bestDiagonalIdx;

				if (bestIdx == ~0ul)
				{
					if (vertexCount != 3)
						break;

					bestIdx = 1;
				}
			}

			{
				const size_t a = bestIdx ? (bestIdx - 1) : (vertexCount - 1);
				const size_t b = bestIdx;
				const size_t c = (bestIdx + 1) % vertexCount;

				assert(a < MaxIndices);
				assert(b < MaxIndices);
				assert(c < MaxIndices);

				const uint16 i0 = indices[a];
				const uint16 i1 = indices[b];
				const uint16 i2 = indices[c];

				PolygonVertex& v0 = contour[i0];
				PolygonVertex& v1 = contour[i1];
				PolygonVertex& v2 = contour[i2];

				uint16 v0i = InsertUniqueVertex(lookUp, v0.x - borderH, v0.y - borderH, v0.z - borderV);
				uint16 v2i = InsertUniqueVertex(lookUp, v1.x - borderH, v1.y - borderH, v1.z - borderV);
				uint16 v1i = InsertUniqueVertex(lookUp, v2.x - borderH, v2.y - borderH, v2.z - borderV);

				--vertexCount;

				if ((v0i == v1i) | (v0i == v2i) | (v1i == v2i))
				{
					if (vertexCount < 3)
						break;

					continue;
				}

				m_triangles.resize(m_triangles.size() + 1);
				Tile::Triangle& triangle = m_triangles.back();

				triangle.linkCount = 0;
				triangle.firstLink = 0;

				triangle.vertex[0] = v0i;
				triangle.vertex[1] = v1i;
				triangle.vertex[2] = v2i;

				if (vertexCount < 3)
					break;

				for (size_t k = bestIdx; k < vertexCount; ++k)
					indices[k] = indices[k + 1];

				const uint16 updi0 = bestIdx ? (bestIdx - 1) : (vertexCount - 1);
				const uint16 updi2 = bestIdx % vertexCount;

				contour[indices[updi0]].flags &= ~(PolygonVertex::Reflex | PolygonVertex::Ear);
				if (IsReflex(updi0, &contour[0], indices, vertexCount))
					contour[indices[updi0]].flags |= PolygonVertex::Reflex;
				else if (IsEar(updi0, &contour[0], contour.size(), indices, vertexCount, agentHeight))
					contour[indices[updi0]].flags |= PolygonVertex::Ear;

				contour[indices[updi2]].flags &= ~(PolygonVertex::Reflex | PolygonVertex::Ear);
				if (IsReflex(updi2, &contour[0], indices, vertexCount))
					contour[indices[updi2]].flags |= PolygonVertex::Reflex;
				else if (IsEar(updi2, &contour[0], contour.size(), indices, vertexCount, agentHeight))
					contour[indices[updi2]].flags |= PolygonVertex::Ear;

				++triCount;
			}
		}

		return triCount;
	}

	bool TileGenerator::MergeHole(PolygonContour& contour, const PolygonContour& hole, const size_t agentHeight,
		const size_t holeVertex) const
	{
		const size_t holeSize = hole.size();
		const size_t contourSize = contour.size();

		const PolygonVertex& hv = hole[holeVertex];
		
		size_t closest = ~0ul;
		real_t edgeFrac = real_t::max();
		real_t distClosest = real_t::max();

		size_t heightAdd = 0;
		const size_t heightStep = 4;
		const size_t limitHeight = (size_t)((float)m_params.sizeZ / m_params.voxelSize.z) * 2;
		
		while (heightAdd < limitHeight)
		{
			for (size_t i = 0; i < contourSize; ++i)
			{
				const PolygonVertex& v0 = contour[i];
				const PolygonVertex& v1 = contour[(i + 1) % contourSize];

				const size_t minZ = std::min<size_t>(v0.z, v1.z);
				const size_t maxZ = std::max<size_t>(v0.z, v1.z);

				if ((hv.z > maxZ + agentHeight + heightAdd) || (hv.z + agentHeight + heightAdd < minZ))
					continue;

				if ((v0.y < hv.y) || (v1.y > hv.y))
					continue;

				real_t s, t;

				if (v0.y > hv.y)
				{
					if (v1.y < hv.y)
					{
						s = real_t(v0.y - hv.y) / real_t(v0.y - v1.y);
						t = real_t(v0.x - hv.x) + s * (v1.x - v0.x);
					}
					else
					{
						t = v1.x - hv.x;
						s = 1;
					}
				}
				else
				{
					if (v1.y < hv.y)
					{
						t = v0.x - hv.x;
						s = 0;
					}
					else
					{
						if (v0.x < v1.x)
						{
							t = v0.x - hv.x;
							s = 0;
						}
						else
						{
							t = v1.x - hv.x;
							s = 1;
						}
					}
				}

				if ((t >= 0) && (t < distClosest))
				{
					closest = i;
					distClosest = t;
					edgeFrac = s;
				}
			}

			if (closest != ~0ul)
				break;

			heightAdd += heightStep;
		}
	
		uint16 polyVertex = 0;
		if (edgeFrac == 0)
		{
			polyVertex = closest;
		}
		else if (edgeFrac == 1)
		{
			polyVertex = (closest + 1) % contourSize;
		}
		else if (closest != ~0ul)
		{
			const PolygonVertex& v0 = contour[closest];
			const PolygonVertex& v1 = contour[(closest + 1) % contourSize];

			const vector2_t p0(hv.x, hv.y);
			const vector2_t mid = vector2_t(p0.x + distClosest, p0.y);

			vector2_t start;
			vector2_t end;
			size_t endIndex;
			
			if ((v0.x > v1.x) || ((v0.x == v1.x) && (v0.y < v1.y)))
			{
				endIndex = closest;
				end = vector2_t(v0.x, v0.y);
			}
			else
			{
				endIndex = (closest + 1) % contourSize;
				end = vector2_t(v1.x, v1.y);
			}

			const size_t minZ = std::min<size_t>(std::min<size_t>(hv.z, v0.z), v1.z);
			const size_t maxZ = std::max<size_t>(std::max<size_t>(hv.z, v0.z), v1.z);

			size_t best = endIndex;
			real_t bestCos = real_t::min();
			real_t bestLenSq = real_t::max();

			for (size_t i = 1; i < contourSize; ++i)
			{
				const size_t vi = (endIndex + i) % contourSize;
				const PolygonVertex& v = contour[vi];

				if ((v.flags & PolygonVertex::Reflex) == 0)
					continue;

				if ((v.z > maxZ + agentHeight) || (v.z + agentHeight < minZ))
					continue;

				const vector2_t vv(v.x, v.y);

				if (PointInTriangle(vv, p0, mid, end))
				{
					const vector2_t diff = vv - p0;
					const real_t lenSq = diff.lenSq();
					const real_t cs = sqr(vv.x) / lenSq;

					if ((cs > bestCos) || ((cs == bestCos) && (lenSq < bestLenSq)))
					{
						best = vi;
						bestLenSq = lenSq;
						bestCos = cs;
					}
				}
			}

			polyVertex = best;
		}
		else
		{
			return false;
		}


		contour.reserve(contourSize + holeSize + 2);

		size_t ip = polyVertex + 1;
		contour.insert(contour.begin() + ip, hole.rbegin() + (holeSize - holeVertex - 1), hole.rend());
		ip += holeVertex + 1;

		contour.insert(contour.begin() + ip, hole.rbegin(), hole.rbegin() + (holeSize - holeVertex));
		ip += holeSize - holeVertex;

		contour.insert(contour.begin() + ip, contour[polyVertex]);

		return true;
	}

	size_t TileGenerator::Triangulate()
	{
		m_profiler.StartTimer(Triangulation);
		
		size_t totalIndexCount = 0;
		size_t vertexCount = 0;

		for (size_t i = 0; i < m_polygons.size(); ++i)
		{
			const PolygonContour& contour = m_polygons[i].contour;
			const PolygonHoles& holes = m_polygons[i].holes;

			totalIndexCount += (contour.size() - 2) * 3;
			vertexCount += contour.size();

			for (size_t h = 0; h < holes.size(); ++h)
			{
				totalIndexCount += holes[h].size() * 3;
				vertexCount += holes[h].size() + 2;
			}
		}

		VertexIndexLookUp lookUp;
		lookUp.reset(vertexCount, vertexCount);

		m_triangles.clear();
		m_triangles.reserve(totalIndexCount);

		m_vertices.clear();
		m_vertices.reserve(vertexCount);

		size_t triCount = 0;

		const size_t agentHeight = m_params.agent.height;
		const size_t borderH = BorderSizeH();
		const size_t borderV = BorderSizeV();

		for (size_t p = 0; p < m_polygons.size(); ++p)
		{
			Polygon& polygon = m_polygons[p];
			PolygonHoles& holes = polygon.holes;
			PolygonContour& contour = polygon.contour;

			size_t contourSize = contour.size();

			size_t finalVertexCount = contourSize;
			for (size_t h = 0; h < holes.size(); ++h)
				finalVertexCount += holes[h].size() + 2;
			contour.reserve(finalVertexCount);

			for (size_t v = 0; v < contourSize; v++)
			{
				contour[v].flags &= ~PolygonVertex::Reflex;
				contour[v].flags |= IsReflex(v, &contour[0], contourSize) ? PolygonVertex::Reflex : 0;
			}

			while (!holes.empty())
			{
				uint16 bestHole = ~0;
				uint16 bestHoleVertex = 0;
				uint16 bestHoleVertexX = 0;

				for (size_t h = 0; h < holes.size(); ++h)
				{
					const PolygonContour& hole = holes[h];
				
					uint16 holeVertex = 0;

					for (size_t i = 1; i < hole.size(); ++i)
					{
						if ((hole[i].x > hole[holeVertex].x) || ((hole[i].x == hole[holeVertex].x) && (hole[i].y > hole[holeVertex].y)))
							holeVertex = i;
					}

					if (hole[holeVertex].x > bestHoleVertexX)
					{
						bestHole = h;
						bestHoleVertex = holeVertex;
						bestHoleVertexX = hole[holeVertex].x;
					}

					assert(bestHole < polygon.holes.size());
				}

				if (MergeHole(contour, holes[bestHole], agentHeight, bestHoleVertex))
				{
					std::swap(holes[bestHole], holes.back());
					holes.pop_back();

					contourSize = contour.size();

					for (size_t v = 0; v < contourSize; v++)
					{
						contour[v].flags &= ~PolygonVertex::Reflex;
						contour[v].flags |= IsReflex(v, &contour[0], contourSize) ? PolygonVertex::Reflex : 0;
					}
				}
				else
				{
					std::swap(holes[bestHole], holes.back());
					holes.pop_back();
				}

			}

			for (size_t v = 0; v < contourSize; v++)
			{
				PolygonVertex& vv = contour[v];
				if ((vv.flags & PolygonVertex::Reflex) == 0)
					vv.flags |= IsEar(v, &contour[0], contourSize, agentHeight) ? PolygonVertex::Ear : 0;
			}

			triCount += Triangulate(polygon.contour, agentHeight, borderH, borderV, lookUp);
		}

		m_profiler.StopTimer(Triangulation);

		m_profiler.AddMemory(TriangulationMemory, lookUp.size() * sizeof(VertexIndexLookUp::value_type));
		m_profiler.FreeMemory(TriangulationMemory, lookUp.size() * sizeof(VertexIndexLookUp::value_type));

		m_profiler.AddMemory(TriangleMemory, m_triangles.capacity() * sizeof(Triangles::value_type));
		m_profiler.AddMemory(VertexMemory, m_vertices.capacity() * sizeof(Vertices::value_type));

		m_profiler.AddStat(VertexCount, m_vertices.size());
		m_profiler.AddStat(TriangleCount, m_triangles.size());
		
		return triCount;
	}

	struct BVTriangle
	{
		BVTriangle(uint16 _triangleID = 0, uint16 _binID = 0)
			: triangleID(_triangleID)
			, binID(_binID)
		{
		}

		uint16 triangleID;
		uint16 binID;

		vector3_t centroid;
		aabb_t aabb;


		bool operator<(const BVTriangle& other) const
		{
			return binID < other.binID;
		}
	};

	struct BVBin
	{
		BVBin()
			: area(0)
			, triCount(0)
			, leftArea(0)
			, leftTriCount(0)
			, aabb(aabb_t::init_empty())
		{
		}

		aabb_t aabb;

		real_t area;
		size_t triCount;

		real_t leftArea;
		size_t leftTriCount;
	};


	struct sort_triangle_by_dimension
	{
		sort_triangle_by_dimension(size_t _dim)
			: dim(_dim)
		{
		}

		bool operator()(const BVTriangle& left, const BVTriangle& right) const
		{
			if (left.centroid[dim] == right.centroid[dim])
				return left.aabb.min[dim] < right.aabb.min[dim];

			return left.centroid[dim] < right.centroid[dim];
		}

		size_t dim;
	};

	void CalculateVolume(const BVTriangle* triangles, size_t firstTri, size_t triCount, aabb_t& aabb)
	{
		aabb = aabb_t(aabb_t::init_empty());

		const size_t triEnd = firstTri + triCount;
		for (size_t i = firstTri; i < triEnd; ++i)
			aabb += triangles[i].aabb;
	}

	void SplitSAH(const aabb_t& aabb, BVTriangle* triangles, size_t firstTri, size_t triCount,
		Tile::BVNode* nodes, size_t& nodeCount)
	{
		Tile::BVNode& node = nodes[nodeCount++];
		node.aabb = aabb;
		
		assert(!aabb.empty());
		assert(!node.aabb.empty());

		if (triCount == 1)
		{
			node.leaf = 1;
			node.offset = triangles[firstTri].triangleID;

			return;
		}

		node.leaf = 0;
		
		aabb_t caabb = aabb_t::init_empty();

		for (size_t i = firstTri; i < firstTri + triCount; ++i)
			caabb += triangles[i].centroid;

		const vector3_t size(aabb.size());
		size_t dimSplit = 0;

		if (size.y >= size.z)
		{
			if (size.y > size.x)
				dimSplit = 1;
		}
		else if (size.z > size.x)
			dimSplit = 2;

		const real_t distCentroid = caabb.max[dimSplit] - caabb.min[dimSplit];

		const size_t MaxBinCount = 8;
		BVBin bins[MaxBinCount];

		const real_t BinEpsilon = real_t::fraction(1, 1000);
		const size_t BinCount = distCentroid > BinEpsilon ? 8 : 2;
		const real_t BinConv = (distCentroid > 0) ? (real_t(static_cast<unsigned int>(BinCount)) - BinEpsilon) / distCentroid : 0;

		for (size_t i = firstTri; i < firstTri + triCount; ++i)
		{
			BVTriangle& tri = triangles[i];

			const real_t centroid = tri.centroid[dimSplit] - caabb.min[dimSplit];
			const size_t binID = (BinConv * centroid).as_uint();
			assert(binID < BinCount);

			tri.binID = binID;

			BVBin& bin = bins[binID];
			++bin.triCount;

			bin.aabb += tri.aabb;
		}

		// find split plane
		real_t leftArea(0);
		size_t leftTriCount = 0;

		{
			aabb_t laabb = aabb_t::init_empty();

			for (size_t i = 0; i < BinCount; ++i)
			{
				BVBin& bin = bins[i];

				if (bin.triCount)
				{
					const vector3_t dims(bin.aabb.size());
					const real_t area = (dims.x * dims.y + dims.x * dims.z + dims.z * dims.y) * 2;
					bin.area = area;

					leftArea += area;
					leftTriCount += bin.triCount;

					bin.leftArea = leftArea;
					bin.leftTriCount = leftTriCount;

					laabb += bin.aabb;		
				}

				bin.aabb = laabb;
			}
		}

		real_t costLowest = leftArea * static_cast<unsigned int>(leftTriCount);
		size_t split = BinCount - 1;

		aabb_t raabbLowest = aabb_t::init_empty();
		aabb_t raabb = aabb_t::init_empty();

		real_t rightArea(0);
		size_t rightTriCount = 0;

		for (size_t i = 0; i < BinCount - 2; ++i)
		{
			const BVBin& bin = bins[BinCount - i - 1];
			if (!bin.triCount)
				continue;

			raabb += bin.aabb;

			const BVBin& left = bins[BinCount - i - 2];

			rightArea += bin.area;
			rightTriCount = bin.triCount;

			const real_t cost = rightArea * static_cast<unsigned int>(rightTriCount) + bin.leftArea * static_cast<unsigned int>(bin.leftTriCount);

			if (cost < costLowest)
			{
				costLowest = cost;
				split = BinCount - i - 2; // split at the right side of the bin

				raabbLowest += raabb;
			}
		}

		size_t currentNode = nodeCount - 1;

		if (split == BinCount - 1)
		{
			std::sort(triangles + firstTri, triangles + firstTri + triCount, sort_triangle_by_dimension(dimSplit));

			size_t splitTri = triCount >> 1;

			aabb_t laabb;
			CalculateVolume(triangles, firstTri, splitTri, laabb);
			SplitSAH(laabb, triangles, firstTri, splitTri, nodes, nodeCount);

			CalculateVolume(triangles, firstTri + splitTri, triCount - splitTri, raabb);
			SplitSAH(raabb, triangles, firstTri + splitTri, triCount - splitTri, nodes, nodeCount);
			node.offset = nodeCount - currentNode;
		}
		else
		{
			std::sort(triangles + firstTri, triangles + firstTri + triCount);

			size_t splitTri = std::distance(triangles + firstTri, 
				std::lower_bound(triangles + firstTri, triangles + firstTri + triCount, BVTriangle(0, split + 1)));
			assert(splitTri < triCount);

			SplitSAH(bins[split].aabb, triangles, firstTri, splitTri, nodes, nodeCount);
			SplitSAH(raabbLowest, triangles, firstTri + splitTri, triCount - splitTri, nodes, nodeCount);
			node.offset = nodeCount - currentNode;
		}
	}

	void TileGenerator::BuildBVTree()
	{
		m_profiler.StartTimer(BVTreeConstruction);

		const size_t triangleCount = m_triangles.size();
		
		if (!triangleCount)
		{
			BVTree().swap(m_bvtree);
			
			return;
		}

		aabb_t aabb = aabb_t::init_empty();

		std::vector<BVTriangle> bvTriangles;
		bvTriangles.resize(triangleCount);

		for (size_t i = 0; i < triangleCount; ++i)
		{
			const Tile::Triangle& triangle = m_triangles[i];
			BVTriangle& bvTri = bvTriangles[i];

			vector3_t vertices[3];

			for (size_t v = 0; v < 3; ++v)
				vertices[v] = vector3_t(m_vertices[triangle.vertex[v]]);

			bvTri.aabb = aabb_t(
				vector3_t::minimize(vertices[0], vertices[1], vertices[2]),
				vector3_t::maximize(vertices[0], vertices[1], vertices[2]));
			bvTri.centroid = bvTri.aabb.center();
			bvTri.triangleID = i;

			aabb += bvTri.aabb;
		}

		assert(aabb.min.x >= 0);
		assert(aabb.min.y >= 0);
		assert(aabb.min.z >= 0);

		assert(aabb.max.x <= m_params.sizeX);
		assert(aabb.max.y <= m_params.sizeY);
		assert(aabb.max.z <= m_params.sizeZ);

		std::vector<Tile::BVNode> nodes(2 * triangleCount);
		size_t nodeCount = 0;

		SplitSAH(aabb, &bvTriangles.front(), 0, bvTriangles.size(), &nodes.front(), nodeCount);
		nodes.resize(nodeCount);

		m_profiler.StopTimer(BVTreeConstruction);

		m_profiler.AddMemory(BVTreeMemory, nodes.size() * sizeof(Tile::BVNode));
		m_profiler.AddStat(BVTreeNodeCount, nodes.size());

		m_profiler.AddMemory(BVTreeConstructionMemory, nodes.capacity() * sizeof(Tile::BVNode));
		m_profiler.FreeMemory(BVTreeConstructionMemory, nodes.capacity() * sizeof(Tile::BVNode));

		m_bvtree = nodes;
	}
}
